Low-density parity-check (LDPC) codes are linear error correcting block codes that may be used to transmit data over a noisy transmission channel. LDPC codes are defined by a generator matrix and a sparse parity check matrix. On the transmit/encoding side of a network, the codeword of an input string may be obtained by multiplying the input bit string by the generator matrix. In other words, given a k-bit message i={i0, i1, i2, . . . , ik-1} that is a vector of length k, a codeword C(i) may be obtained by the expression C(i)=iG, where G is the generator matrix. For example, suppose that i is the three-bit message 010 and G=
      (                            1                          0                          0                          1                          1                          1                                      0                          1                          0                          1                          1                          0                                      0                          0                          1                          1                          0                          1                      )    .Then the codeword C(i) is 010110 where the first three bits 010 are the original information bits and the last three bits 110 are parity bits obtained from the three information bits.
As the codeword is transmitted over a noisy transmission channel, errors may be introduced into the codeword such that the received vector of bits on the receiver/decoding side is not same as the original codeword (e.g. 1s in positions that should be 0s and 0s in positions that should be 1s.) On the receiver/decoder side of LDPC coding, the parity check matrix may be used to determine if a given received vector of bits is a valid codeword (i.e., has no errors). This can be expressed as HC(i)t=0 where H is r×n parity check matrix, where r=n−k is the number of parity bits in the codeword, n is the number of total bits in the codeword, and C(i)t is the transpose of the received vector. Each row of the parity check matrix H represents an equation that must be satisfied while each column represents bits in the received codeword.
The parity check matrix may be used to correct errors in received vectors. As shown in FIG. 1, for a particular parity check matrix H, this process of converging on a codeword may be illustrated by a bipartite graph, comprising bit nodes and parity nodes, where each bit node represents a code symbol and each parity node represents a parity equation. A line is drawn between a bit node and a check node if the bit is involved in the parity equation, and decoding is accomplished by passing messages along the lines of the graph.
From check nodes m to bit nodes n, each check node may provide to a connected bit node an estimate of the value of that bit node (i.e., probability that the bit node is 0 or 1) based on the information received from other connected bit nodes. For example, using the illustrated example of FIG. 1, if the sum of n4, n5 and n8 is believed to be 0 to m1, then m1 would indicate to n1 that the value of n1 is believed to be 0 (because this satisfies the parity equation n1+n4+n5+n8=0); otherwise m1 will indicate to n1 that the value of n1 is believed to be 1.
From bit nodes n to check nodes m, each bit node may broadcast to connected check nodes an estimate of its own value based on the information received from other connected check nodes. In the above example, n1 is connected to check nodes m1 and m3. If the information received from m3 to n1 indicates that there is a high probability that the value of n1 is 0, then n1 would notify m1 that an estimate of n1 's value is 0. As another example, in cases where the bit node has more than two connected check nodes, the bit node may rely on a majority vote (soft decision) the feedback coming from its other connected check nodes before reporting that soft decision to the check node. The above process may be repeated iteratively until all bit nodes are considered to be correct (i.e., all parity check equations are satisfied) or until a predetermined maximum number of iterations is reached, whereby a decoding failure may be declared.
Standard belief decoding is an LDPC decoding scheme that applies the process described above. In SBD, the decoder works through each and every one of the rows of the parity check matrix, one by one. After working through every row of the parity check matrix, the bit nodes are then updated and the process may iterate. By contrast, in the more recently developed LDPC layered-belief decoding (LBD) scheme, information gained going through each row of the parity check matrix (i.e., each equation) may be used when making decisions in subsequent rows. Particularly, after solving a parity equation for one row, soft decisions on bit nodes are stored and made available so that the decoder may use this information immediately when considering another row (i.e., check node) of the parity check matrix. This process is described in greater detail in U.S. Pat. No. 8,402,341. Consequently, LBD typically converges on a codeword using about half as many iterations as SBD. Additionally, in LBD, each iteration takes about roughly half the time as in SBD, thus providing much higher throughput. Accordingly, LBD may provide significant advantages over SBD.